1. Field of the Invention
This invention relates generally to encoders and decoders for cyclic block codes of the Bose-Chaudhuri-Hocquenghem (BCH) type and, more particularly, to serial encoders and decoders with single error correcting capability.
2. Description of the Prior Art
Most of the prior art relating to BCH-type encoders and decoders concentrate on binary division techniques for generating the parity check bits at the encoder, and the syndrome, as well as shifted versions thereof, at the decoder. Largely ignored in the prior art are the necessary logical functions needed to maintain synchronism between bits of the code word generated at the encoder and the corresponding synchronizing functions required at the decoder to process the sequentially received data blocks.
Prior to 1972, binary division was typically accomplished by distributing a series of exclusive OR gates along a shift register cascade. With this arrangement, division at the encoder utilizes an augmented version of the input data as the dividend and the code generator word as the divisor. During each step of the division, the leading bit of the partial remainder is fed back to the numerous exclusive OR gates embedded within the shift register string. This conventional arrangement requires a significant number of exclusive OR circuits, particularly for code generator words that are densely distributed.
With the advent of high-speed magnetic bubble devices, it became inefficient to use a large number of exclusive OR gates and unduly complicated logic. Instead, a single exclusive OR gate was utilized in a serial encoding arrangement that was first described in a paper by the applicant. The paper, entitled "The Design and Embodiment of Magnetic Domain Encoders for Single-Error Correcting Decoders for Cyclic Block Codes," was published in the February, 1972 issue of the Bell System Technical Journal and represents the most pertinent prior art reference. The paper presents an encoder topology utilizing a single exclusive OR gate; however, the topology is specifically arranged for use with magnetic domain technology. The topology is dictated by a constraint imposed by the technology which requires all bits of information to be propagated by one period in one clock cycle. Thus, although magnetic domain technology offers inexpensive storage, this technology requires significant time intervals for every operation (generation, propagation, sensing, annihilation, and so forth) in contrast to the essentially instantaneous operation of semiconductor circuitry. Moreover, the ability of semiconductor shift registers to shift in at one rate and shift out at another rate is not utilized with such a topology.
In addition, the encoder topology presented in the paper is for the special case wherein the number of parity bits is sufficiently large compared to the number of data bits. To efficiently utilize channel capacity, it is desirable that the number of parity bits be small relative to the number of data bits. Neither applicant's paper nor other prior art teaches or suggests a serial encoding arrangement for efficient channel utilization.
The paper also discusses the binary division process utilized in a decoder. Besides elucidating a conventional decoder of the type wherein a series of exclusive OR gates is embedded in a shift register string, a specifically designed serial decoder adapted for use with the constraints of magnetic domain technology is presented. The aforementioned restrictions discussed with respect to magnetic domain encoders also apply with respect to decoders.
Furthermore, the paper only alluded to the need for a technique to synchronize the interaction of an encoder-decoder pair comprising a transmission system. No synchronizing plan was set forth for perusal.